package com.buddy.summary.code.algorithm;

/**
 * 给出两个很大的整数，要求实现程序求出两个整数的和
 */
public class Algorithm_09 {

    public static String bigNumSum(String bigNumA, String bigNumB) {
        //1.把两个大整数用数组逆序存储，存储长度等于较大整数位数+1
        int maxLength = bigNumA.length() > bigNumB.length() ? bigNumA.length() : bigNumB.length();
        int[] arrA = new int[maxLength + 1];
        //逆序存储A和B
        for (int i = 0; i < bigNumA.length(); i++) {
            arrA[i] = bigNumA.charAt(bigNumA.length() - 1 - i) - '0';
        }
        int[] arrB = new int[maxLength + 1];
        for (int i = 0; i < bigNumB.length(); i++) {
            arrB[i] = bigNumB.charAt(bigNumB.length() - 1 - i) - '0';
        }
        //2.构建result数组，数组长度等于maxLength+1，放置最后一位进位
        int[] result = new int[maxLength + 1];
        //3.遍历数组按位相加
        for (int i=0;i<result.length;i++){
            int temp = result[i];
            temp += arrA[i];
            temp += arrB[i];
            if (temp > 10){
                temp = temp - 10;
                result[i+1] = i;
            }
            result[i] = temp;
        }

        //4.把result数组再次逆序并转成String
        StringBuilder sb = new StringBuilder();
        //最高位是否有效
        boolean findFirst = false;
        for (int i = result.length -1;i>=0;i--){
            if (!findFirst){
                if (result[i] == 0){
                    continue;
                }
                findFirst = true;
            }
            sb.append(result[i]);
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        System.out.println(bigNumSum("123","456"));
    }
}
